package com.cold.demo.web.util;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author Cold
 * @Email 378661553@qq.com
 * @Date Created in 2019/9/20 17:18
 */
public class TreeUtil {

    /**
     * @param list
     * @param root
     * @param <T>  必须实现 Tree 接口才能够有用
     * @return
     */
    public static <T> T setTree(List<T> list, T root) {
        if (!(root instanceof Tree)) {
            throw new RuntimeException("Item in list does not implement TreeUtil.Tree");
        }
        if (list==null){
            return root;
        }
        List<Tree> tempList = new ArrayList<>();
        list.forEach(t -> tempList.add((Tree) t));
        Tree ptmTree = doSetTree(tempList, (Tree) root);
        return (T) ptmTree;
    }

    /**
     *
     * @param list 除去根节点的所有数据
     * @param root 根节点
     */
    private static Tree doSetTree(List<Tree> list, Tree root) {
        // key 主键id,value 子集parentId与key一致的节点集合
        Map<Integer, List<Tree>> map = new HashMap<>(list.size());
        for (Tree ptmTree : list) {
            List<Tree> ptmTrees = map.computeIfAbsent(ptmTree.getParentId(), k -> new ArrayList<>());
            ptmTrees.add(ptmTree);
        }
        setChildren(root, map);
        return root;
    }

    /**
     * set 子集
     * @param treeRoot
     * @param map
     */
    private static void setChildren(Tree treeRoot, Map<Integer, List<Tree>> map) {
        List<Tree> children = map.get(treeRoot.getId());
        if (children != null && children.size() > 0) {
            for (Tree child : children) {
                setChildren(child, map);
            }
        }
        treeRoot.setChildren(children);
    }

    public interface Tree<T> {
        /**
         * id
         */
        Integer getId();

        /**
         * 上级id
         */
        Integer getParentId();

        /**
         * set子集
         */
        void setChildren(List<T> children);
    }
}
